class Solution(object):
    def maxValue(self, n, index, maxSum):
        left = 1
        right = maxSum
        def search(val):
            if val > index:
                left_val = (2 * val - index) * (index + 1) // 2
            else:
                left_val = (val + 1) * val // 2 + index + 1 - val
            if val > (n - index):
                right_val = (2 * val - (n - index - 1)) * (n - index) // 2
            else:
                right_val = (val + 1) * val // 2 + n - index - val
            return left_val + right_val - val <= maxSum

        while left < right:
            mid = (left + right + 1) // 2
            if search(mid):
                left = mid
            else:
                right = mid - 1
        return left